import java.util.*;

/**
 * Created by qtbui on 2017/9/21.
 */

class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution
{
	private Map<Integer,List<Integer>> m_Level=new HashMap<>();

	public List<List<Integer>> levelOrderBottom(TreeNode root)
	{
		if(root==null)
		{
			return new ArrayList<>();
		}

		getMaxDepth(root,1);

		List<List<Integer>> result=new ArrayList<>();

		for(int i=m_Level.size();i>=1;--i)
		{
			result.add(m_Level.get(i));
		}

		return result;
	}

	public void getMaxDepth(TreeNode tn, int level)
	{
		if(tn==null)
		{
			return;
		}

		if(m_Level.containsKey(level))
		{
			m_Level.get(level).add(tn.val);
		}
		else
		{
			List<Integer> valList=new ArrayList<>();
			valList.add(tn.val);
			m_Level.put(level,valList);
		}

		getMaxDepth(tn.left,level+1);
		getMaxDepth(tn.right,level+1);

	}
}

public class test
{
    public static void main(String[] args)
    {
		TreeNode tn=new TreeNode(0);
		tn.left=new TreeNode(1);
		tn.right=new TreeNode(1);
		tn.left.left=new TreeNode(2);
		tn.left.right=new TreeNode(3);
		tn.right.left=new TreeNode(3);
		tn.right.right=new TreeNode(2);

		System.out.println(new Solution().maxDepth(tn));
    }
}
